/*
 *  Copyright (C) 2010 Martin Haulrich <mwh.isv@cbs.dk>
 *
 *  This file is part of the MatrixParser package.
 *
 *  The MatrixParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.osdtsystem.matrixparser.parsers;

import java.util.List;
import org.osdtsystem.matrixparser.data.CONLLSentence;
import org.osdtsystem.matrixparser.parsers.output.DependencyTree;
import org.osdtsystem.matrixparser.featureextraction.FirstOrderExtractorLabelled;
import org.osdtsystem.matrixparser.featureextraction.FirstOrderExtractorUnlabelled;
import org.osdtsystem.matrixparser.features.FeatureVector;
import org.osdtsystem.matrixparser.features.MstCache;
import org.osdtsystem.matrixparser.features.TwoWayFeatureHandler;
import org.osdtsystem.matrixparser.learners.Scorer;
import org.osdtsystem.matrixparser.features.WeightVector;
import org.osdtsystem.matrixparser.mst.ChuLiuEdmonds;

/**
 * 
 * @author Martin Haulrich
 */
public class MSTParser extends AbstractParser {
    public MSTParser(String name, Scorer scorer, FirstOrderExtractorUnlabelled unlabelledMstExtractor,
            FirstOrderExtractorLabelled labelledMstExtractor, TwoWayFeatureHandler labelAlphabet) {
        super(name, scorer, unlabelledMstExtractor, labelledMstExtractor, labelAlphabet);
    }

    public DependencyTree parse(CONLLSentence sentence,
            WeightVector weightVector) {
        // Retrieve feature cache
        MstCache cache =
                mstCache(sentence);
        
        // Compute edge-factored scores
        int nodes = sentence.size();
        double[][] scores = new double[nodes][nodes];
        for (int i = 0; i < nodes; i++) {
            for (int j = 0; j < nodes; j++) {
                scores[i][j] = scorer.getScore(weightVector,
                        cache.unlabelledFeatures(i, j));
            }
        }

        // Run Chu-Liu-Edmonds algorithm
        List<Integer> CLEheads = ChuLiuEdmonds.chuLiuEdmonds(scores);
        
        // Return tree
        DependencyTree tree = new DependencyTree(sentence, labelAlphabet, lastComplementId);
        for (int i = 1; i < CLEheads.size(); i++) {
            tree.setDependency(i, CLEheads.get(i), 0);
        }
        return tree;
    }

    @Override
    List<FeatureVector> featureVectors(DependencyTree tree, List<FeatureVector> aggregator) {
        CONLLSentence sentence = tree.sentence();
        MstCache cache = mstCache(sentence);
        for (int node = 1; node < tree.nodes(); ++ node) {
            int head = tree.head(node);
            if (head >= 0)
                aggregator.add(cache.unlabelledFeatures(head, node));
        }
        return aggregator;
    }
}
